package com.cn.algorithm02.class13;

import com.cn.algorithm02.class01.Nodea;

import java.util.LinkedList;

/***
 * @author: hels
 * @description: 判断是否为完全二叉树  Compelete Binary Tree
 * 完全二叉树，按层遍历节点是连续的
 **/
public class C01_IsCBT {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        Nodea head = Nodea.getNodeInstance(arr);

        head.right.right = null;
        head.right.left = new Nodea(55);
        Nodea.printTree(head);

        System.out.println(isCBT(head));

    }

    public static boolean isCBT (Nodea head) {
        if (head == null) return true;

        LinkedList<Nodea> queue = new LinkedList<>();
        queue.add(head);
        Nodea l = null;
        Nodea r = null;
        Nodea current = null;
        // 是否遇到非全叶子的节点
        boolean state = false;

        while (!queue.isEmpty()) {
            current = queue.poll();
            l = current.left;
            r = current.right;

            if ( (l == null && r != null) || (state && ( l != null || r != null))) {
                return false;
            }

            if (l == null || r == null) {
                state = true;
            }

            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }

        }


        return true;
    }
}
